package net.xuele.learn.dancing.window;

import java.util.*;

/**
 * @Author: yubo
 * @date: 13:44 2020/12/23
 * @Description: 类描述：76、最小覆盖子串
 * <p>
 * 移动窗口的核心思想：先
 */

public class MinWindow {


    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        int sLen = s.length();
        while (right < sLen) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 二者数量相等，valid++
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 右移窗口
            right++;
            // 判断左侧是否要收缩
            // valid == need.size()表示子串的所有字符全部都在window中了
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d)))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }
                // 左移窗口
                left++;
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ?
                "" : s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "cbaebabacd", t = "abc";
        String l = "pwwkew";
        System.out.println(new MinWindow().lengthOfLongestSubstring(l));
    }


    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int pLen = p.length();
        for (int i = 0; i < pLen; i++) {
            char c = p.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int right = 0, left = 0, valid = 0;
        int length = s.length();
        while (right < length) {
            char r = s.charAt(right);
            if (need.containsKey(r)) {
                window.put(r, window.getOrDefault(r, 0) + 1);
                if (window.get(r).equals(need.get(r))) {
                    valid++;
                }
            }
            right++;
            // 窗口最小是p的长度
            while (right - left >= pLen) {

                if (valid == need.size()) {
                    result.add(left);
                }
                char l = s.charAt(left);

                if (need.containsKey(l)) {
                    if (window.get(l).equals(need.get(l))) {
                        valid--;
                    }
                    window.put(l, window.get(l) - 1);
                }
                left++;
            }
        }
        return result;
    }


    public int lengthOfLongestSubstring(String s) {
        int right = 0, left = 0;
        int max = 0;
        int length = s.length();
        while (right < length) {
            char c = s.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            while (window.get(c) > 1) {
                char l = s.charAt(left);
                left++;
                window.put(l, window.get(l) - 1);
            }
            // 在这里更新答案
            max = Math.max(max, right - left);
        }

        return max;
    }

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrace(nums, track);
        return res;
    }

    private void backtrace(int[] nums, LinkedList<Integer> track) {
        // 触发结束条件：nums 中的元素全都在 track 中出现
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            // 排除不合法的选择
            if (track.contains(num)) {
                continue;
            }
            track.add(num);
            // 进入下一层决策树
            backtrace(nums, track);
            // 取消选择
            track.removeLast();
        }

    }

}
